﻿namespace Graph;

//对无向图进行拓扑排序,判断无向图中是否存在环时，是将所有度 <= 1 的结点入队。
//对有向图进行拓扑排序，判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。
public class TopSort
{
    private IGraph G;
    private int[] inDegree;
    private Stack<int> stack = new Stack<int>(); //也可用Queue<int>

    public MyList<int> ResultList { get; } = new MyList<int>();
    public bool HasCycle { get; private set; }
    public bool CanTopSort { get; private set; }

    public TopSort(IGraph G)
    {
        this.G = G;        

        inDegree = new int[G.V];
        for (int i = 0; i < G.V; i++)
        {
            if (G is IDiGraph diG)
            {
                inDegree[i] = diG.InDegree(i);
            }
            else
            {
                inDegree[i] = G.Degree(i);
            }
        }

        for (int i = 0; i < G.V; i++)
        {
            if (G is IDiGraph)
            {
                if (inDegree[i] == 0)
                {
                    stack.Push(i);
                }
            }
            else
            {
                if (inDegree[i] <= 1)
                {
                    stack.Push(i);
                }
            }
        }

        while (stack.Count != 0)
        {
            int v = stack.Pop();
            ResultList.Add(v);
            foreach (int w in G.Adj(v))
            {
                inDegree[w]--;
                if (G is IDiGraph)
                {
                    if (inDegree[w] == 0)
                    {
                        stack.Push(w);
                    }
                }
                else
                {
                    if (inDegree[w] == 1)
                    {
                        stack.Push(w);
                    }
                }
            }
        }

        if (ResultList.Count < G.V)
        {
            HasCycle = true;
        }
        else
        {
            CanTopSort = true;
        }
    }

    //验证
    static void Main(string[] args)
    {
        //IGraph graph = new AdjLinkList("无向无权图/g4.txt");
        IDiGraph graph = new DiAdjLinkList("有向无权图/无权有环图.txt");
        Console.WriteLine(graph);
        TopSort topSort = new TopSort(graph);

        if (topSort.HasCycle)
        {
            Console.WriteLine("有环,无拓扑序列!");
            return;
        }
        else
        {
            Console.Write("拓扑序列是：");
        }

        Console.WriteLine(topSort.ResultList);

        Console.Read();
    }
}
